package com.wenhai.leetcode.linkedList;

/**
 * @ClassName _86分隔链表
 * @Description https://leetcode-cn.com/problems/partition-list/  https://leetcode-cn.com/problems/partition-list-lcci/
 * @Author 谢文海
 * @Date 2021/4/4 20:50
 * @Version 1.0
 **/
public class _86分隔链表 {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        ListNode lHead = new ListNode(0);
        ListNode lTail = lHead;
        ListNode rHead = new ListNode(0);
        ListNode rTail = rHead;
        while (head != null) {
            if (head.val < x) {
                lTail.next = head;
                lTail = lTail.next;
            } else {
                rTail.next = head;
                rTail = rTail.next;
            }
            head = head.next;
        }
        rTail.next = null;
        lTail.next = rHead.next;
        return lHead.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }


}
